/**
 This file was a modified version of "stb_truetype.h". ("external/stb")
 What changed?
 1. c => c++
 2. c pointer buffer (malloc,free) => c++ vector.
 3. visit unsafe data pointer, segment error => checked and throw.
 */

#include "zen_truetype.h"
#include "zen_exception.h"
#include "zen_log.h"
#include <stdlib.h>
#include <math.h>

#include <string.h>

namespace Zen {

#define tt__tag4(p,c0,c1,c2,c3) ((p)[0] == (c0) && (p)[1] == (c1) && (p)[2] == (c2) && (p)[3] == (c3))
#define tt__tag(p,str) tt__tag4(p,str[0],str[1],str[2],str[3])

	struct Iterator {
		long pos = 0;
		std::vector<uint8_t> * ref = nullptr;

		bool good(long index = 0) {
			if(!ref) return false;
			long p = pos + index;
			return !(p < 0 || p >= ref->size());
		}

		uint8_t & operator [] (long index)
		{
			musts(good(index), "");
			return ref->at(pos + index);
		}
		uint8_t & operator * () {
			musts(good(), "");
			return ref->at(pos);
		}
		long index() {
			return pos;
		}
		Iterator operator + (long move)
		{
			Iterator r;
			r.pos = pos + move;
			r.ref = ref;
			return r;
		}
		Iterator operator - (long move)
		{
			return *this + (-move);
		}
		long operator - (Iterator o) {
			return pos - o.pos;
		}
		Iterator(std::vector<uint8_t> & v, int index = 0) {
			pos = index;
			ref = &v;
		}
		Iterator()
		{
			pos = 0;
			ref = nullptr;
		}
		Iterator operator ++(int) {
			Iterator r = *this;
			++pos;
			return r;
		}
		Iterator & operator ++() {
			++pos;
			return *this;
		}
		Iterator & operator +=(long index)
		{
			pos += index;
			return *this;
		}
		Iterator operator --(int) {
			Iterator r = *this;
			--pos;
			return r;
		}
		Iterator & operator --() {
			--pos;
			return *this;
		}
		Iterator & operator -=(long index)
		{
			pos -= index;
			return *this;
		}
	};

	enum TTTypeV {
		vmove=1,
		vline,
		vcurve,
		vcubic
	};

	struct TTEdge {
		float x0,y0, x1,y1;
		int invert;
	};

	struct TTHeadHeapChunk
	{
		struct TTHeadHeapChunk *next;
	};

	struct TTHeadHeap
	{
		struct TTHeadHeapChunk *head;
		void   *first_free;
		int    num_remaining_in_head_chunk;
	};


	struct TTActiveEdge
	{
		std::shared_ptr<TTActiveEdge> next;

		float fx,fdx,fdy;
		float direction;
		float sy;
		float ey;

	};

	struct TTBuf
	{
		size_t data_i;
		int cursor = 0;
		int size = 0;
	} ;
	struct TTFontInfo
	{
		void           * userdata;
		std::vector<uint8_t> data;              // pointer to .ttf file
		int              fontstart;         // offset of start of font

		int numGlyphs;                     // number of glyphs, needed for range checking

		int loca,head,glyf,hhea,hmtx,kern,gpos; // table locations as offset from start of .ttf
		int index_map;                     // a cmap mapping for our chosen character encoding
		int indexToLocFormat;              // format needed to map from glyph index to glyph

		TTBuf cff;                    // cff font data
		TTBuf charstrings;            // the charstring index
		TTBuf gsubrs;                 // global charstring subroutines index
		TTBuf subrs;                  // private charstring subroutines index
		TTBuf fontdicts;              // array of font dicts
		TTBuf fdselect;               // map from glyph to fontdict
	};

	typedef short TTVertexType; // can't use int16_t because that's not visible in the header file

	struct TTVertex
	{
		TTVertexType x,y,cx,cy,cx1,cy1;
		unsigned char type,padding;
	};

	struct TTContext
	{
		int bounds; /// if bounds == 1, no pvertices.
		int started;
		float first_x, first_y;
		float x, y;
		int32_t min_x, max_x, min_y, max_y;

		std::vector<TTVertex> pvertices;
		int num_vertices;
	};
	inline TTContext TTContextInit(int bounds)
	{ return {bounds,0, 0,0, 0,0, 0,0,0,0, {}, 0}; }

	struct TrueType_i : TrueType {

		TTFontInfo m_info;
		TTFontInfo * info;

		VMetrics m_metrics;

		TrueType_i()
		{
			info = &m_info;
		}

		enum { // platformID
			STBTT_PLATFORM_ID_UNICODE   =0,
			STBTT_PLATFORM_ID_MAC       =1,
			STBTT_PLATFORM_ID_ISO       =2,
			STBTT_PLATFORM_ID_MICROSOFT =3
		};
		enum { // encodingID for STBTT_PLATFORM_ID_MICROSOFT
			STBTT_MS_EID_SYMBOL        =0,
			STBTT_MS_EID_UNICODE_BMP   =1,
			STBTT_MS_EID_SHIFTJIS      =2,
			STBTT_MS_EID_UNICODE_FULL  =10
		};

		void check(Iterator p, long sz)
		{
			if(!p.good() || !p.good(sz-1)) throw std::out_of_range("truetype read out");
		}
		uint16_t toUint16(Iterator p) { check(p, 2); return p[0]*256 + p[1]; }
		int16_t toInt16(Iterator p)   { check(p, 2); return p[0]*256 + p[1]; }
		uint32_t toUint32(Iterator p) { check(p, 4); return (p[0]<<24) + (p[1]<<16) + (p[2]<<8) + p[3]; }
		int32_t toInt32(Iterator p)   { check(p, 4); return (p[0]<<24) + (p[1]<<16) + (p[2]<<8) + p[3]; }
		uint8_t toUint8(Iterator p)   { check(p, 1); return (uint8_t)p[0]; }
		int8_t toInt8(Iterator p)     { check(p, 1); return (int8_t)p[0]; }

		TTBuf createBuf(size_t index, size_t size)
		{
			TTBuf r;
			r.data_i = index;
			r.size = (int) size;
			r.cursor = 0;
			return r;
		}
		TTBuf createBuf(Iterator p, size_t size)
		{
			TTBuf r;
			r.data_i = p.index();
			r.size = (int) size;
			r.cursor = 0;
			return r;
		}
		
		uint32_t tt___find_table(Iterator data, uint32_t fontstart, const char *tag)
		{
			int32_t num_tables = toUint16(data+fontstart+4);
			uint32_t tabledir = fontstart + 12;
			int32_t i;
			for (i=0; i < num_tables; ++i) {
				uint32_t loc = tabledir + 16*i;
				if (tt__tag(data+loc+0, tag))
					return toUint32(data+loc+8);
			}
			return 0;
		}
		
		uint8_t TTBuf_get8(TTBuf *b)
		{
			if (b->cursor >= b->size)
				return 0;
			return m_info.data.at(b->data_i + b->cursor++);
		}
		
		uint8_t TTBuf_peek8(TTBuf *b)
		{
			if (b->cursor >= b->size)
				return 0;
			return m_info.data.at(b->data_i + b->cursor);
		}
		
		void TTBuf_seek(TTBuf *b, int o)
		{
			must(!(o > b->size || o < 0));
			b->cursor = (o > b->size || o < 0) ? b->size : o;
		}
		
		void TTBuf_skip(TTBuf *b, int o)
		{
			TTBuf_seek(b, b->cursor + o);
		}
		
		uint32_t TTBuf_get(TTBuf *b, int n)
		{
			uint32_t v = 0;
			int i;
			must(n >= 1 && n <= 4);
			for (i = 0; i < n; i++)
				v = (v << 8) | TTBuf_get8(b);
			return v;
		}

		inline uint32_t TTBuf_get16(TTBuf * b) { return TTBuf_get((b), 2); }
		inline uint32_t TTBuf_get32(TTBuf * b) { return TTBuf_get((b), 4); }
		
		TTBuf TTBuf_range(TTBuf *b, int o, int s)
		{
			if (o < 0 || s < 0 || o > b->size || s > b->size - o)
				return createBuf(0, 0);
			return createBuf(b->data_i + o, s);
		}
		
		uint32_t tt___cff_int(TTBuf *b)
		{
			int b0 = TTBuf_get8(b);
			if (b0 >= 32 && b0 <= 246)       return b0 - 139;
			else if (b0 >= 247 && b0 <= 250) return (b0 - 247)*256 + TTBuf_get8(b) + 108;
			else if (b0 >= 251 && b0 <= 254) return -(b0 - 251)*256 - TTBuf_get8(b) - 108;
			else if (b0 == 28)               return TTBuf_get16(b);
			else if (b0 == 29)               return TTBuf_get32(b);
			must(0);
			return 0;
		}
		void tt___cff_skip_operand(TTBuf *b) {
			int v, b0 = TTBuf_peek8(b);
			must(b0 >= 28);
			if (b0 == 30) {
				TTBuf_skip(b, 1);
				while (b->cursor < b->size) {
					v = TTBuf_get8(b);
					if ((v & 0xF) == 0xF || (v >> 4) == 0xF)
						break;
				}
			} else {
				tt___cff_int(b);
			}
		}
		
		TTBuf tt___dict_get(TTBuf *b, int key)
		{
			TTBuf_seek(b, 0);
			while (b->cursor < b->size) {
				int start = b->cursor, end, op;
				while (TTBuf_peek8(b) >= 28)
					tt___cff_skip_operand(b);
				end = b->cursor;
				op = TTBuf_get8(b);
				if (op == 12)  op = TTBuf_get8(b) | 0x100;
				if (op == key) return TTBuf_range(b, start, end-start);
			}
			return TTBuf_range(b, 0, 0);
		}
		
		TTBuf tt___cff_index_get(TTBuf b, int i)
		{
			int count, offsize, start, end;
			TTBuf_seek(&b, 0);
			count = TTBuf_get16(&b);
			offsize = TTBuf_get8(&b);
			must(i >= 0 && i < count);
			must(offsize >= 1 && offsize <= 4);
			TTBuf_skip(&b, i*offsize);
			start = TTBuf_get(&b, offsize);
			end = TTBuf_get(&b, offsize);
			return TTBuf_range(&b, 2+(count+1)*offsize+start, end - start);
		}
		TTBuf tt___cff_get_index(TTBuf *b)
		{
			int count, start, offsize;
			start = b->cursor;
			count = TTBuf_get16(b);
			if (count) {
				offsize = TTBuf_get8(b);
				must(offsize >= 1 && offsize <= 4);
				TTBuf_skip(b, offsize * count);
				TTBuf_skip(b, TTBuf_get(b, offsize) - 1);
			}
			return TTBuf_range(b, start, b->cursor - start);
		}
		void tt___dict_get_ints(TTBuf *b, int key, int outcount, uint32_t *out)
		{
			int i;
			TTBuf operands = tt___dict_get(b, key);
			for (i = 0; i < outcount && operands.cursor < operands.size; i++)
				out[i] = tt___cff_int(&operands);
		}
		
		
		TTBuf tt___get_subrs(TTBuf cff, TTBuf fontdict)
		{
			uint32_t subrsoff = 0, private_loc[2] = { 0, 0 };
			TTBuf pdict;
			tt___dict_get_ints(&fontdict, 18, 2, private_loc);
			if (!private_loc[1] || !private_loc[0]) return createBuf(NULL, 0);
			pdict = TTBuf_range(&cff, private_loc[1], private_loc[0]);
			tt___dict_get_ints(&pdict, 19, 1, &subrsoff);
			if (!subrsoff) return createBuf(NULL, 0);
			TTBuf_seek(&cff, private_loc[1]+subrsoff);
			return tt___cff_get_index(&cff);
		}

		inline void _check_position(uint32_t p, const char * error)
		{
			musts(p > 0 && p < m_info.data.size(), error);
		}
		inline void _check_position0(uint32_t p, const char * error)
		{
			musts(p >= 0 && p < m_info.data.size(), error);
		}
		bool tt__InitFont_internal()
		{
			int fontstart = 0;

			Iterator data(info->data);

			info->fontstart = fontstart;
			info->cff = createBuf(NULL, 0);
			
			auto cmap = tt___find_table(data, fontstart, "cmap");  // required
			info->loca = tt___find_table(data, fontstart, "loca"); // required
			info->head = tt___find_table(data, fontstart, "head"); // required
			info->glyf = tt___find_table(data, fontstart, "glyf"); // required
			info->hhea = tt___find_table(data, fontstart, "hhea"); // required
			info->hmtx = tt___find_table(data, fontstart, "hmtx"); // required
			info->kern = tt___find_table(data, fontstart, "kern"); // not required
			info->gpos = tt___find_table(data, fontstart, "GPOS"); // not required

			_check_position(cmap, "error truetype camp");
			_check_position(info->loca, "error truetype loca");
			_check_position(info->head, "error truetype head");
			_check_position(info->glyf, "error truetype glyf");
			_check_position(info->hhea, "error truetype hhea");
			_check_position(info->hmtx, "error truetype hmtx");
			_check_position0(info->kern, "error truetype kern");
			_check_position0(info->gpos, "error truetype gpos");

			if (info->glyf) {
				// required for truetype
				if (!info->loca) return 0;
			} else {
				// initialization for CFF / Type2 fonts (OTF)
				TTBuf b, topdict, topdictidx;
				uint32_t cstype = 2, charstrings = 0, fdarrayoff = 0, fdselectoff = 0;
				uint32_t cff;
				
				cff = tt___find_table(data, fontstart, "CFF ");
				if (!cff) return 0;
				
				info->fontdicts = createBuf(NULL, 0);
				info->fdselect = createBuf(NULL, 0);
				
				// @TODO this should use size from table (not 512MB)
				info->cff = createBuf(data+(int)cff, 512*1024*1024);
				b = info->cff;
				
				// read the header
				TTBuf_skip(&b, 2);
				TTBuf_seek(&b, TTBuf_get8(&b)); // hdrsize
				
				// @TODO the name INDEX could list multiple fonts,
				// but we just use the first one.
				tt___cff_get_index(&b);  // name INDEX
				topdictidx = tt___cff_get_index(&b);
				topdict = tt___cff_index_get(topdictidx, 0);
				tt___cff_get_index(&b);  // string INDEX
				info->gsubrs = tt___cff_get_index(&b);
				
				tt___dict_get_ints(&topdict, 17, 1, &charstrings);
				tt___dict_get_ints(&topdict, 0x100 | 6, 1, &cstype);
				tt___dict_get_ints(&topdict, 0x100 | 36, 1, &fdarrayoff);
				tt___dict_get_ints(&topdict, 0x100 | 37, 1, &fdselectoff);
				info->subrs = tt___get_subrs(b, topdict);
				
				// we only support Type 2 charstrings
				if (cstype != 2) return 0;
				if (charstrings == 0) return 0;
				
				if (fdarrayoff) {
					// looks like a CID font
					if (!fdselectoff) return 0;
					TTBuf_seek(&b, fdarrayoff);
					info->fontdicts = tt___cff_get_index(&b);
					info->fdselect = TTBuf_range(&b, fdselectoff, b.size-fdselectoff);
				}
				
				TTBuf_seek(&b, charstrings);
				info->charstrings = tt___cff_get_index(&b);
			}
			
			auto t = tt___find_table(data, fontstart, "maxp");
			if (t)
				info->numGlyphs = toUint16(data+t+4);
			else
				info->numGlyphs = 0xffff;
			
			//			info->svg = -1;
			
			// find a cmap encoding table we understand *now* to avoid searching
			// later. (todo: could make this installable)
			// the same regardless of glyph.
			int32_t numTables = toUint16(data + cmap + 2);
			info->index_map = 0;
			for (int i=0; i < numTables; ++i) {
				uint32_t encoding_record = cmap + 4 + 8 * i;
				// find an encoding we understand:
				switch(toUint16(data+encoding_record)) {
					case STBTT_PLATFORM_ID_MICROSOFT:
						switch (toUint16(data+encoding_record+2)) {
							case STBTT_MS_EID_UNICODE_BMP:
							case STBTT_MS_EID_UNICODE_FULL:
								// MS/Unicode
								info->index_map = cmap + toUint32(data+encoding_record+4);
								break;
						}
						break;
					case STBTT_PLATFORM_ID_UNICODE:
						// Mac/iOS has these
						// all the encodingIDs are unicode, so we don't bother to check it
						info->index_map = cmap + toUint32(data+encoding_record+4);
						break;
				}
			}
			musts(!(info->index_map == 0 || info->index_map > info->data.size()), "error index_map");
			
			info->indexToLocFormat = toUint16(data+info->head + 50);

			static const int METRICS_VALUE_LIMIT = (1<<13);

			m_metrics.ascent  = toInt16(data+info->hhea + 4); // + top
			m_metrics.height = m_metrics.ascent - toInt16(data+info->hhea + 6);
			m_metrics.lineGap = toInt16(data+info->hhea + 8);

			musts(::abs(m_metrics.ascent) < METRICS_VALUE_LIMIT, "error ascent");
			musts(m_metrics.height > 0 && m_metrics.height < METRICS_VALUE_LIMIT, "error height");
			musts(::abs(m_metrics.lineGap) < METRICS_VALUE_LIMIT, "error line gap");
			return true;
		}
		void tt__GetGlyphHMetrics(int glyph_index, int *advanceWidth, int *leftSideBearing)
		{
			Iterator data = m_info.data;
			uint16_t numOfLongHorMetrics = toUint16(data+info->hhea + 34);
			if (glyph_index < numOfLongHorMetrics) {
				if (advanceWidth)     *advanceWidth    = toInt16(data + info->hmtx + 4*glyph_index);
				if (leftSideBearing)  *leftSideBearing = toInt16(data + info->hmtx + 4*glyph_index + 2);
			} else {
				if (advanceWidth)     *advanceWidth    = toInt16(data + info->hmtx + 4*(numOfLongHorMetrics-1));
				if (leftSideBearing)  *leftSideBearing = toInt16(data + info->hmtx + 4*numOfLongHorMetrics + 2*(glyph_index - numOfLongHorMetrics));
			}
		}

		void tt___track_vertex(TTContext *c, int32_t x, int32_t y)
		{
			if (x > c->max_x || !c->started) c->max_x = x;
			if (y > c->max_y || !c->started) c->max_y = y;
			if (x < c->min_x || !c->started) c->min_x = x;
			if (y < c->min_y || !c->started) c->min_y = y;
			c->started = 1;
		}
		
		void tt__setvertex(TTVertex *v, uint8_t type, int32_t x, int32_t y, int32_t cx, int32_t cy)
		{
			v->type = type;
			v->x = (int16_t) x;
			v->y = (int16_t) y;
			v->cx = (int16_t) cx;
			v->cy = (int16_t) cy;
		}
		void tt___csctx_v(TTContext *c, uint8_t type, int32_t x, int32_t y, int32_t cx, int32_t cy, int32_t cx1, int32_t cy1)
		{
			if (c->bounds) {
				tt___track_vertex(c, x, y);
				if (type == TTTypeV::vcubic) {
					tt___track_vertex(c, cx, cy);
					tt___track_vertex(c, cx1, cy1);
				}
			} else {
				tt__setvertex(&c->pvertices[c->num_vertices], type, x, y, cx, cy);
				c->pvertices[c->num_vertices].cx1 = (int16_t) cx1;
				c->pvertices[c->num_vertices].cy1 = (int16_t) cy1;
			}
			c->num_vertices++;
		}
		
		void tt___csctx_rline_to(TTContext *ctx, float dx, float dy)
		{
			ctx->x += dx;
			ctx->y += dy;
			tt___csctx_v(ctx, TTTypeV::vline, (int)ctx->x, (int)ctx->y, 0, 0, 0, 0);
		}
		
		void tt___csctx_rccurve_to(TTContext *ctx, float dx1, float dy1, float dx2, float dy2, float dx3, float dy3)
		{
			float cx1 = ctx->x + dx1;
			float cy1 = ctx->y + dy1;
			float cx2 = cx1 + dx2;
			float cy2 = cy1 + dy2;
			ctx->x = cx2 + dx3;
			ctx->y = cy2 + dy3;
			tt___csctx_v(ctx, TTTypeV::vcubic, (int)ctx->x, (int)ctx->y, (int)cx1, (int)cy1, (int)cx2, (int)cy2);
		}
		
		int tt___GetGlyfOffset(const int glyph_index)
		{
			int g1,g2;
			
			must(!info->cff.size);
			Iterator data = m_info.data;
			if (glyph_index >= info->numGlyphs) return -1; // glyph index out of range
			if (info->indexToLocFormat >= 2)    return -1; // unknown index->glyph map format
			
			if (info->indexToLocFormat == 0) {
				g1 = info->glyf + toUint16(data + info->loca + glyph_index * 2) * 2;
				g2 = info->glyf + toUint16(data + info->loca + glyph_index * 2 + 2) * 2;
			} else {
				g1 = info->glyf + toUint32 (data + info->loca + glyph_index * 4);
				g2 = info->glyf + toUint32 (data + info->loca + glyph_index * 4 + 4);
			}
			
			return g1==g2 ? -1 : g1; // if length is 0, return -1
		}
		
		
		int tt___close_shape(TTVertex *vertices, int num_vertices, int was_off, int start_off,
							 int32_t sx, int32_t sy, int32_t scx, int32_t scy, int32_t cx, int32_t cy)
		{
			if (start_off) {
				if (was_off)
					tt__setvertex(&vertices[num_vertices++], TTTypeV::vcurve, (cx+scx)>>1, (cy+scy)>>1, cx,cy);
				tt__setvertex(&vertices[num_vertices++], TTTypeV::vcurve, sx,sy,scx,scy);
			} else {
				if (was_off)
					tt__setvertex(&vertices[num_vertices++], TTTypeV::vcurve,sx,sy,cx,cy);
				else
					tt__setvertex(&vertices[num_vertices++], TTTypeV::vline,sx,sy,0,0);
			}
			return num_vertices;
		}
		
		int tt___GetGlyphShapeTT(const int glyph_index, std::vector<TTVertex> * pvertices)
		{
			int16_t numberOfContours;
			Iterator data = info->data;
			Iterator endPtsOfContours = data + info->data.size();

			std::vector<TTVertex> vertices;
			int num_vertices=0;
			int g = tt___GetGlyfOffset(glyph_index);
			
			pvertices->clear();

			if (g < 0) return 0;
			
			numberOfContours = toInt16(data + g);
			
			if (numberOfContours > 0) {
				uint8_t flags=0,flagcount;
				int32_t ins, i,j=0,m,n, next_move, was_off=0, off, start_off=0;
				int32_t x,y,cx,cy,sx,sy, scx,scy;
				//				uint8_t *points;
				endPtsOfContours = (data + (g + 10));
				ins = toUint16(data + (g + 10 + numberOfContours * 2));
				Iterator points = data + (g + 10 + numberOfContours * 2 + 2 + ins);
				
				n = 1+toUint16(endPtsOfContours + numberOfContours*2-2);
				
				m = n + 2*numberOfContours;  // a loose bound on how many vertices we might need
				//				vertices = (TTVertex *) STBTT_malloc(m * sizeof(vertices[0]), info->userdata);
				//				if (vertices == 0)
				//					return 0;
				vertices.resize(m);
				
				next_move = 0;
				flagcount=0;
				
				// in first pass, we load uninterpreted data into the allocated array
				// above, shifted to the end of the array so we won't overwrite it when
				// we create our final data starting from the front
				
				off = m - n; // starting offset for uninterpreted data, regardless of how m ends up being calculated
				
				// first load flags
				
				for (i=0; i < n; ++i) {
					if (flagcount == 0) {
						flags = *points++;
						if (flags & 8)
							flagcount = *points++;
					} else
						--flagcount;
					vertices[off+i].type = flags;
				}
				
				// now load x coordinates
				x=0;
				for (i=0; i < n; ++i) {
					flags = vertices[off+i].type;
					if (flags & 2) {
						int16_t dx = *points++;
						x += (flags & 16) ? dx : -dx; // ???
					} else {
						if (!(flags & 16)) {
							x = x + (int16_t) (points[0]*256 + points[1]);
							points += 2;
						}
					}
					vertices[off+i].x = (int16_t) x;
				}
				
				// now load y coordinates
				y=0;
				for (i=0; i < n; ++i) {
					flags = vertices[off+i].type;
					if (flags & 4) {
						int16_t dy = *points++;
						y += (flags & 32) ? dy : -dy; // ???
					} else {
						if (!(flags & 32)) {
							y = y + (int16_t) (points[0]*256 + points[1]);
							points += 2;
						}
					}
					vertices[off+i].y = (int16_t) y;
				}
				
				// now convert them to our format
				num_vertices=0;
				sx = sy = cx = cy = scx = scy = 0;
				for (i=0; i < n; ++i) {
					flags = vertices[off+i].type;
					x     = (int16_t) vertices[off+i].x;
					y     = (int16_t) vertices[off+i].y;
					
					if (next_move == i) {
						if (i != 0)
							num_vertices = tt___close_shape(vertices.data(), num_vertices, was_off, start_off, sx,sy,scx,scy,cx,cy);
						
						// now start the new one
						start_off = !(flags & 1);
						if (start_off) {
							// if we start off with an off-curve point, then when we need to find a point on the curve
							// where we can start, and we need to save some state for when we wraparound.
							scx = x;
							scy = y;
							if (!(vertices[off+i+1].type & 1)) {
								// next point is also a curve point, so interpolate an on-point curve
								sx = (x + (int32_t) vertices[off+i+1].x) >> 1;
								sy = (y + (int32_t) vertices[off+i+1].y) >> 1;
							} else {
								// otherwise just use the next point as our start point
								sx = (int32_t) vertices[off+i+1].x;
								sy = (int32_t) vertices[off+i+1].y;
								++i; // we're using point i+1 as the starting point, so skip it
							}
						} else {
							sx = x;
							sy = y;
						}
						tt__setvertex(&vertices[num_vertices++], TTTypeV::vmove,sx,sy,0,0);
						was_off = 0;
						next_move = 1 + toUint16(endPtsOfContours+j*2);
						++j;
					} else {
						if (!(flags & 1)) { // if it's a curve
							if (was_off) // two off-curve control points in a row means interpolate an on-curve midpoint
								tt__setvertex(&vertices[num_vertices++], TTTypeV::vcurve, (cx+x)>>1, (cy+y)>>1, cx, cy);
							cx = x;
							cy = y;
							was_off = 1;
						} else {
							if (was_off)
								tt__setvertex(&vertices[num_vertices++], TTTypeV::vcurve, x,y, cx, cy);
							else
								tt__setvertex(&vertices[num_vertices++], TTTypeV::vline, x,y,0,0);
							was_off = 0;
						}
					}
				}
				num_vertices = tt___close_shape(vertices.data(), num_vertices, was_off, start_off, sx,sy,scx,scy,cx,cy);
			} else if (numberOfContours < 0) {
				// Compound shapes.
				int more = 1;
				auto comp = data + g + 10;
				num_vertices = 0;
				vertices.clear();
				while (more) {
					uint16_t flags, gidx;
					int comp_num_verts = 0, i;
					std::vector<TTVertex> comp_verts;
					float mtx[6] = {1,0,0,1,0,0}, m, n;
					
					flags = toInt16(comp); comp+=2;
					gidx = toInt16(comp); comp+=2;
					
					if (flags & 2) { // XY values
						if (flags & 1) { // shorts
							mtx[4] = toInt16(comp); comp+=2;
							mtx[5] = toInt16(comp); comp+=2;
						} else {
							mtx[4] = toInt8(comp); comp+=1;
							mtx[5] = toInt8(comp); comp+=1;
						}
					}
					else {
						// @TODO handle matching point
						must(0);
					}
					if (flags & (1<<3)) { // WE_HAVE_A_SCALE
						mtx[0] = mtx[3] = toInt16(comp)/16384.0f; comp+=2;
						mtx[1] = mtx[2] = 0;
					} else if (flags & (1<<6)) { // WE_HAVE_AN_X_AND_YSCALE
						mtx[0] = toInt16(comp)/16384.0f; comp+=2;
						mtx[1] = mtx[2] = 0;
						mtx[3] = toInt16(comp)/16384.0f; comp+=2;
					} else if (flags & (1<<7)) { // WE_HAVE_A_TWO_BY_TWO
						mtx[0] = toInt16(comp)/16384.0f; comp+=2;
						mtx[1] = toInt16(comp)/16384.0f; comp+=2;
						mtx[2] = toInt16(comp)/16384.0f; comp+=2;
						mtx[3] = toInt16(comp)/16384.0f; comp+=2;
					}
					
					// Find transformation scales.
					m = (float) sqrt(mtx[0]*mtx[0] + mtx[1]*mtx[1]);
					n = (float) sqrt(mtx[2]*mtx[2] + mtx[3]*mtx[3]);
					
					// Get indexed glyph.
					comp_num_verts = tt__GetGlyphShape(gidx, &comp_verts);
					if (comp_num_verts > 0) {
						// Transform vertices.
						for (i = 0; i < comp_num_verts; ++i) {
							TTVertex* v = &comp_verts[i];
							TTVertexType x,y;
							x=v->x; y=v->y;
							v->x = (TTVertexType)(m * (mtx[0]*x + mtx[2]*y + mtx[4]));
							v->y = (TTVertexType)(n * (mtx[1]*x + mtx[3]*y + mtx[5]));
							x=v->cx; y=v->cy;
							v->cx = (TTVertexType)(m * (mtx[0]*x + mtx[2]*y + mtx[4]));
							v->cy = (TTVertexType)(n * (mtx[1]*x + mtx[3]*y + mtx[5]));
						}
						// Append vertices.

						must(vertices.size() == num_vertices);
						must(comp_verts.size() == comp_num_verts);

						vertices.insert(vertices.end(), comp_verts.begin(), comp_verts.end());
						num_vertices += comp_num_verts;
					}
					// More components ?
					more = flags & (1<<5);
				}
			} else {
				// numberOfCounters == 0, do nothing
			}
			
			*pvertices = std::move(vertices);
			return num_vertices;
		}
		
		
		void tt___csctx_close_shape(TTContext *ctx)
		{
			if (ctx->first_x != ctx->x || ctx->first_y != ctx->y)
				tt___csctx_v(ctx, TTTypeV::vline, (int)ctx->first_x, (int)ctx->first_y, 0, 0, 0, 0);
		}
		
		TTBuf tt___cid_get_glyph_subrs(const int glyph_index)
		{
			TTBuf fdselect = info->fdselect;
			int nranges, start, end, v, fmt, fdselector = -1, i;
			
			TTBuf_seek(&fdselect, 0);
			fmt = TTBuf_get8(&fdselect);
			if (fmt == 0) {
				// untested
				TTBuf_skip(&fdselect, glyph_index);
				fdselector = TTBuf_get8(&fdselect);
			} else if (fmt == 3) {
				nranges = TTBuf_get16(&fdselect);
				start = TTBuf_get16(&fdselect);
				for (i = 0; i < nranges; i++) {
					v = TTBuf_get8(&fdselect);
					end = TTBuf_get16(&fdselect);
					if (glyph_index >= start && glyph_index < end) {
						fdselector = v;
						break;
					}
					start = end;
				}
			}
			if (fdselector == -1) createBuf(NULL, 0);
			return tt___get_subrs(info->cff, tt___cff_index_get(info->fontdicts, fdselector));
		}
		
		void tt___csctx_rmove_to(TTContext *ctx, float dx, float dy)
		{
			tt___csctx_close_shape(ctx);
			ctx->first_x = ctx->x = ctx->x + dx;
			ctx->first_y = ctx->y = ctx->y + dy;
			tt___csctx_v(ctx, TTTypeV::vmove, (int)ctx->x, (int)ctx->y, 0, 0, 0, 0);
		}
		
		
		int tt___cff_index_count(TTBuf *b)
		{
			TTBuf_seek(b, 0);
			return TTBuf_get16(b);
		}
		TTBuf tt___get_subr(TTBuf idx, int n)
		{
			int count = tt___cff_index_count(&idx);
			int bias = 107;
			if (count >= 33900)
				bias = 32768;
			else if (count >= 1240)
				bias = 1131;
			n += bias;
			if (n < 0 || n >= count)
				return createBuf(NULL, 0);
			return tt___cff_index_get(idx, n);
		}
		
		inline int tt__charstring_error(char const * s)
		{
			Zen::LogE("error: %s", s);
			return 0;
		}
		int tt___run_charstring(const int glyph_index, TTContext *c)
		{
			int in_header = 1, maskbits = 0, subr_stack_height = 0, sp = 0, v, i, b0;
			int has_subrs = 0, clear_stack;
			float s[48];
			TTBuf subr_stack[10], subrs = info->subrs, b;
			float f;

			// this currently ignores the initial width value, which isn't needed if we have hmtx
			b = tt___cff_index_get(info->charstrings, glyph_index);
			while (b.cursor < b.size) {
				i = 0;
				clear_stack = 1;
				b0 = TTBuf_get8(&b);
				switch (b0) {
						// @TODO implement hinting
					case 0x13: // hintmask
					case 0x14: // cntrmask
						if (in_header)
							maskbits += (sp / 2); // implicit "vstem"
						in_header = 0;
						TTBuf_skip(&b, (maskbits + 7) / 8);
						break;
						
					case 0x01: // hstem
					case 0x03: // vstem
					case 0x12: // hstemhm
					case 0x17: // vstemhm
						maskbits += (sp / 2);
						break;
						
					case 0x15: // rmoveto
						in_header = 0;
						if (sp < 2) return tt__charstring_error("rmoveto stack");
						tt___csctx_rmove_to(c, s[sp-2], s[sp-1]);
						break;
					case 0x04: // vmoveto
						in_header = 0;
						if (sp < 1) return tt__charstring_error("vmoveto stack");
						tt___csctx_rmove_to(c, 0, s[sp-1]);
						break;
					case 0x16: // hmoveto
						in_header = 0;
						if (sp < 1) return tt__charstring_error("hmoveto stack");
						tt___csctx_rmove_to(c, s[sp-1], 0);
						break;
						
					case 0x05: // rlineto
						if (sp < 2) return tt__charstring_error("rlineto stack");
						for (; i + 1 < sp; i += 2)
							tt___csctx_rline_to(c, s[i], s[i+1]);
						break;
						
						// hlineto/vlineto and vhcurveto/hvcurveto alternate horizontal and vertical
						// starting from a different place.
						
					case 0x07: // vlineto
						if (sp < 1) return tt__charstring_error("vlineto stack");
						goto vlineto;
					case 0x06: // hlineto
						if (sp < 1) return tt__charstring_error("hlineto stack");
						for (;;) {
							if (i >= sp) break;
							tt___csctx_rline_to(c, s[i], 0);
							i++;
						vlineto:
							if (i >= sp) break;
							tt___csctx_rline_to(c, 0, s[i]);
							i++;
						}
						break;
						
					case 0x1F: // hvcurveto
						if (sp < 4) return tt__charstring_error("hvcurveto stack");
						goto hvcurveto;
					case 0x1E: // vhcurveto
						if (sp < 4) return tt__charstring_error("vhcurveto stack");
						for (;;) {
							if (i + 3 >= sp) break;
							tt___csctx_rccurve_to(c, 0, s[i], s[i+1], s[i+2], s[i+3], (sp - i == 5) ? s[i + 4] : 0.0f);
							i += 4;
						hvcurveto:
							if (i + 3 >= sp) break;
							tt___csctx_rccurve_to(c, s[i], 0, s[i+1], s[i+2], (sp - i == 5) ? s[i+4] : 0.0f, s[i+3]);
							i += 4;
						}
						break;
						
					case 0x08: // rrcurveto
						if (sp < 6) return tt__charstring_error("rcurveline stack");
						for (; i + 5 < sp; i += 6)
							tt___csctx_rccurve_to(c, s[i], s[i+1], s[i+2], s[i+3], s[i+4], s[i+5]);
						break;
						
					case 0x18: // rcurveline
						if (sp < 8) return tt__charstring_error("rcurveline stack");
						for (; i + 5 < sp - 2; i += 6)
							tt___csctx_rccurve_to(c, s[i], s[i+1], s[i+2], s[i+3], s[i+4], s[i+5]);
						if (i + 1 >= sp) return tt__charstring_error("rcurveline stack");
						tt___csctx_rline_to(c, s[i], s[i+1]);
						break;
						
					case 0x19: // rlinecurve
						if (sp < 8) return tt__charstring_error("rlinecurve stack");
						for (; i + 1 < sp - 6; i += 2)
							tt___csctx_rline_to(c, s[i], s[i+1]);
						if (i + 5 >= sp) return tt__charstring_error("rlinecurve stack");
						tt___csctx_rccurve_to(c, s[i], s[i+1], s[i+2], s[i+3], s[i+4], s[i+5]);
						break;
						
					case 0x1A: // vvcurveto
					case 0x1B: // hhcurveto
						if (sp < 4) return tt__charstring_error("(vv|hh)curveto stack");
						f = 0.0;
						if (sp & 1) { f = s[i]; i++; }
						for (; i + 3 < sp; i += 4) {
							if (b0 == 0x1B)
								tt___csctx_rccurve_to(c, s[i], f, s[i+1], s[i+2], s[i+3], 0.0);
							else
								tt___csctx_rccurve_to(c, f, s[i], s[i+1], s[i+2], 0.0, s[i+3]);
							f = 0.0;
						}
						break;
						
					case 0x0A: // callsubr
						if (!has_subrs) {
							if (info->fdselect.size)
								subrs = tt___cid_get_glyph_subrs(glyph_index);
							has_subrs = 1;
						}
						// fallthrough
					case 0x1D: // callgsubr
						if (sp < 1) return tt__charstring_error("call(g|)subr stack");
						v = (int) s[--sp];
						if (subr_stack_height >= 10) return tt__charstring_error("recursion limit");
						subr_stack[subr_stack_height++] = b;
						b = tt___get_subr(b0 == 0x0A ? subrs : info->gsubrs, v);
						if (b.size == 0) return tt__charstring_error("subr not found");
						b.cursor = 0;
						clear_stack = 0;
						break;
						
					case 0x0B: // return
						if (subr_stack_height <= 0) return tt__charstring_error("return outside subr");
						b = subr_stack[--subr_stack_height];
						clear_stack = 0;
						break;
						
					case 0x0E: // endchar
						tt___csctx_close_shape(c);
						return 1;
						
					case 0x0C: { // two-byte escape
						float dx1, dx2, dx3, dx4, dx5, dx6, dy1, dy2, dy3, dy4, dy5, dy6;
						float dx, dy;
						int b1 = TTBuf_get8(&b);
						switch (b1) {
								// @TODO These "flex" implementations ignore the flex-depth and resolution,
								// and always draw beziers.
							case 0x22: // hflex
								if (sp < 7) return tt__charstring_error("hflex stack");
								dx1 = s[0];
								dx2 = s[1];
								dy2 = s[2];
								dx3 = s[3];
								dx4 = s[4];
								dx5 = s[5];
								dx6 = s[6];
								tt___csctx_rccurve_to(c, dx1, 0, dx2, dy2, dx3, 0);
								tt___csctx_rccurve_to(c, dx4, 0, dx5, -dy2, dx6, 0);
								break;
								
							case 0x23: // flex
								if (sp < 13) return tt__charstring_error("flex stack");
								dx1 = s[0];
								dy1 = s[1];
								dx2 = s[2];
								dy2 = s[3];
								dx3 = s[4];
								dy3 = s[5];
								dx4 = s[6];
								dy4 = s[7];
								dx5 = s[8];
								dy5 = s[9];
								dx6 = s[10];
								dy6 = s[11];
								//fd is s[12]
								tt___csctx_rccurve_to(c, dx1, dy1, dx2, dy2, dx3, dy3);
								tt___csctx_rccurve_to(c, dx4, dy4, dx5, dy5, dx6, dy6);
								break;
								
							case 0x24: // hflex1
								if (sp < 9) return tt__charstring_error("hflex1 stack");
								dx1 = s[0];
								dy1 = s[1];
								dx2 = s[2];
								dy2 = s[3];
								dx3 = s[4];
								dx4 = s[5];
								dx5 = s[6];
								dy5 = s[7];
								dx6 = s[8];
								tt___csctx_rccurve_to(c, dx1, dy1, dx2, dy2, dx3, 0);
								tt___csctx_rccurve_to(c, dx4, 0, dx5, dy5, dx6, -(dy1+dy2+dy5));
								break;
								
							case 0x25: // flex1
								if (sp < 11) return tt__charstring_error("flex1 stack");
								dx1 = s[0];
								dy1 = s[1];
								dx2 = s[2];
								dy2 = s[3];
								dx3 = s[4];
								dy3 = s[5];
								dx4 = s[6];
								dy4 = s[7];
								dx5 = s[8];
								dy5 = s[9];
								dx6 = dy6 = s[10];
								dx = dx1+dx2+dx3+dx4+dx5;
								dy = dy1+dy2+dy3+dy4+dy5;
								if (fabs(dx) > fabs(dy))
									dy6 = -dy;
								else
									dx6 = -dx;
								tt___csctx_rccurve_to(c, dx1, dy1, dx2, dy2, dx3, dy3);
								tt___csctx_rccurve_to(c, dx4, dy4, dx5, dy5, dx6, dy6);
								break;
								
							default:
								return tt__charstring_error("unimplemented");
						}
					} break;
						
					default:
						if (b0 != 255 && b0 != 28 && (b0 < 32 || b0 > 254))
							return tt__charstring_error("reserved operator");
						
						// push immediate
						if (b0 == 255) {
							f = (float)(int32_t)TTBuf_get32(&b) / 0x10000;
						} else {
							TTBuf_skip(&b, -1);
							f = (float)(int16_t)tt___cff_int(&b);
						}
						if (sp >= 48) return tt__charstring_error("push stack overflow");
						s[sp++] = f;
						clear_stack = 0;
						break;
				}
				if (clear_stack) sp = 0;
			}
			return tt__charstring_error("no endchar");
			
#undef tt__charstring_error
		}
		
		int tt___GetGlyphShapeT2(const int glyph_index, std::vector<TTVertex> *pvertices)
		{
			// runs the charstring twice, once to count and once to output (to avoid realloc)
			TTContext count_ctx = TTContextInit(1);
			TTContext output_ctx = TTContextInit(0);
			if (tt___run_charstring(glyph_index, &count_ctx)) {
				output_ctx.pvertices.resize(count_ctx.num_vertices);
				if (tt___run_charstring(glyph_index, &output_ctx)) {
					must(output_ctx.num_vertices == count_ctx.num_vertices);
					*pvertices = std::move(output_ctx.pvertices);
					return output_ctx.num_vertices;
				}
			}
			pvertices->clear();
			return 0;
		}
		
		int tt___GetGlyphInfoT2(const int glyph_index, int *x0, int *y0, int *x1, int *y1)
		{
			TTContext c = TTContextInit(1);
			int r = tt___run_charstring(glyph_index, &c);
			if (x0)  *x0 = r ? c.min_x : 0;
			if (y0)  *y0 = r ? c.min_y : 0;
			if (x1)  *x1 = r ? c.max_x : 0;
			if (y1)  *y1 = r ? c.max_y : 0;
			return r ? c.num_vertices : 0;
		}
		
		
		void tt___add_point(std::vector<Point2> & points, int n, float x, float y)
		{
			if (!points.size()) return; // during first pass, it's unallocated
			points[n].x = x;
			points[n].y = y;
		}
		
		
		// tessellate until threshold p is happy... @TODO warped to compensate for non-linear stretching
		int tt___tesselate_curve(std::vector<Point2> & points, int *num_points, float x0, float y0, float x1, float y1, float x2, float y2, float objspace_flatness_squared, int n)
		{
			// midpoint
			float mx = (x0 + 2*x1 + x2)/4;
			float my = (y0 + 2*y1 + y2)/4;
			// versus directly drawn line
			float dx = (x0+x2)/2 - mx;
			float dy = (y0+y2)/2 - my;
			if (n > 16) // 65536 segments on one curve better be enough!
				return 1;
			if (dx*dx+dy*dy > objspace_flatness_squared) { // half-pixel error allowed... need to be smaller if AA
				tt___tesselate_curve(points, num_points, x0,y0, (x0+x1)/2.0f,(y0+y1)/2.0f, mx,my, objspace_flatness_squared,n+1);
				tt___tesselate_curve(points, num_points, mx,my, (x1+x2)/2.0f,(y1+y2)/2.0f, x2,y2, objspace_flatness_squared,n+1);
			} else {
				tt___add_point(points, *num_points,x2,y2);
				*num_points = *num_points+1;
			}
			return 1;
		}
		
		
		void tt___tesselate_cubic(std::vector<Point2> & points, int *num_points, float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3, float objspace_flatness_squared, int n)
		{
			// @TODO this "flatness" calculation is just made-up nonsense that seems to work well enough
			float dx0 = x1-x0;
			float dy0 = y1-y0;
			float dx1 = x2-x1;
			float dy1 = y2-y1;
			float dx2 = x3-x2;
			float dy2 = y3-y2;
			float dx = x3-x0;
			float dy = y3-y0;
			float longlen = (float) (sqrt(dx0*dx0+dy0*dy0)+sqrt(dx1*dx1+dy1*dy1)+sqrt(dx2*dx2+dy2*dy2));
			float shortlen = (float) sqrt(dx*dx+dy*dy);
			float flatness_squared = longlen*longlen-shortlen*shortlen;
			
			if (n > 16) // 65536 segments on one curve better be enough!
				return;
			
			if (flatness_squared > objspace_flatness_squared) {
				float x01 = (x0+x1)/2;
				float y01 = (y0+y1)/2;
				float x12 = (x1+x2)/2;
				float y12 = (y1+y2)/2;
				float x23 = (x2+x3)/2;
				float y23 = (y2+y3)/2;
				
				float xa = (x01+x12)/2;
				float ya = (y01+y12)/2;
				float xb = (x12+x23)/2;
				float yb = (y12+y23)/2;
				
				float mx = (xa+xb)/2;
				float my = (ya+yb)/2;
				
				tt___tesselate_cubic(points, num_points, x0,y0, x01,y01, xa,ya, mx,my, objspace_flatness_squared,n+1);
				tt___tesselate_cubic(points, num_points, mx,my, xb,yb, x23,y23, x3,y3, objspace_flatness_squared,n+1);
			} else {
				tt___add_point(points, *num_points,x3,y3);
				*num_points = *num_points+1;
			}
		}
		
		// returns number of contours
		std::vector<Point2> tt__FlattenCurves(std::vector<TTVertex> & vertices, int num_verts, float objspace_flatness, std::vector<int> *contour_lengths, int *num_contours, void *userdata)
		{
			std::vector<Point2> points;
			int num_points=0;
			
			float objspace_flatness_squared = objspace_flatness * objspace_flatness;
			int i,n=0,start=0, pass;
			
			// count how many "moves" there are to get the contour count
			for (i=0; i < num_verts; ++i)
				if (vertices[i].type == TTTypeV::vmove)
					++n;
			
			*num_contours = n;
			if (n == 0) return {};
			
			contour_lengths->resize(n);

			// make two passes through the points so we don't need to realloc
			for (pass=0; pass < 2; ++pass) {
				float x=0,y=0;
				if (pass == 1) {
					points.resize(num_points);
				}
				num_points = 0;
				n= -1;
				for (i=0; i < num_verts; ++i) {
					switch (vertices[i].type) {
						case TTTypeV::vmove:
							// start the next contour
							if (n >= 0)
								(*contour_lengths)[n] = num_points - start;
							++n;
							start = num_points;
							
							x = vertices[i].x; y = vertices[i].y;
							tt___add_point(points, num_points++, x,y);
							break;
						case TTTypeV::vline:
							x = vertices[i].x; y = vertices[i].y;
							tt___add_point(points, num_points++, x, y);
							break;
						case TTTypeV::vcurve:
							tt___tesselate_curve(points, &num_points, x,y,
												 vertices[i].cx, vertices[i].cy,
												 vertices[i].x,  vertices[i].y,
												 objspace_flatness_squared, 0);
							x = vertices[i].x; y = vertices[i].y;
							break;
						case TTTypeV::vcubic:
							tt___tesselate_cubic(points, &num_points, x,y,
												 vertices[i].cx, vertices[i].cy,
												 vertices[i].cx1, vertices[i].cy1,
												 vertices[i].x,  vertices[i].y,
												 objspace_flatness_squared, 0);
							x = vertices[i].x; y = vertices[i].y;
							break;
					}
				}
				(*contour_lengths)[n] = num_points - start;
			}
			
			return points;
		}
		
#define STBTT__COMPARE(a,b)  ((a)->y0 < (b)->y0)
		
		void tt___sort_edges_ins_sort(TTEdge *p, int n)
		{
			int i,j;
			for (i=1; i < n; ++i) {
				TTEdge t = p[i], *a = &t;
				j = i;
				while (j > 0) {
					TTEdge *b = &p[j-1];
					int c = STBTT__COMPARE(a,b);
					if (!c) break;
					p[j] = p[j-1];
					--j;
				}
				if (i != j)
					p[j] = t;
			}
		}
		
		void tt___sort_edges_quicksort(TTEdge *p, int n)
		{
			/* threshold for transitioning to insertion sort */
			while (n > 12) {
				TTEdge t;
				int c01,c12,c,m,i,j;
				
				/* compute median of three */
				m = n >> 1;
				c01 = STBTT__COMPARE(&p[0],&p[m]);
				c12 = STBTT__COMPARE(&p[m],&p[n-1]);
				/* if 0 >= mid >= end, or 0 < mid < end, then use mid */
				if (c01 != c12) {
					/* otherwise, we'll need to swap something else to middle */
					int z;
					c = STBTT__COMPARE(&p[0],&p[n-1]);
					/* 0>mid && mid<n:  0>n => n; 0<n => 0 */
					/* 0<mid && mid>n:  0>n => 0; 0<n => n */
					z = (c == c12) ? 0 : n-1;
					t = p[z];
					p[z] = p[m];
					p[m] = t;
				}
				/* now p[m] is the median-of-three */
				/* swap it to the beginning so it won't move around */
				t = p[0];
				p[0] = p[m];
				p[m] = t;
				
				/* partition loop */
				i=1;
				j=n-1;
				for(;;) {
					/* handling of equality is crucial here */
					/* for sentinels & efficiency with duplicates */
					for (;;++i) {
						if (!STBTT__COMPARE(&p[i], &p[0])) break;
					}
					for (;;--j) {
						if (!STBTT__COMPARE(&p[0], &p[j])) break;
					}
					/* make sure we haven't crossed */
					if (i >= j) break;
					t = p[i];
					p[i] = p[j];
					p[j] = t;
					
					++i;
					--j;
				}
				/* recurse on smaller side, iterate on larger */
				if (j < (n-i)) {
					tt___sort_edges_quicksort(p,j);
					p = p+i;
					n = n-i;
				} else {
					tt___sort_edges_quicksort(p+i, n-i);
					n = j;
				}
			}
		}
		
		void tt___sort_edges(TTEdge *p, int n)
		{
			tt___sort_edges_quicksort(p, n);
			tt___sort_edges_ins_sort(p, n);
		}

#ifdef _MSC_VER
#define STBTT__NOTUSED(v)  (void)(v)
#else
#define STBTT__NOTUSED(v)  (void)sizeof(v)
#endif

		std::shared_ptr<TTActiveEdge> tt___new_active(TTEdge *e, int off_x, float start_point, void *userdata)
		{
			std::shared_ptr<TTActiveEdge> z(new TTActiveEdge);
			float dxdy = (e->x1 - e->x0) / (e->y1 - e->y0);

			z->fdx = dxdy;
			z->fdy = dxdy != 0.0f ? (1.0f/dxdy) : 0.0f;
			z->fx = e->x0 + dxdy * (start_point - e->y0);
			z->fx -= off_x;
			z->direction = e->invert ? 1.0f : -1.0f;
			z->sy = e->y0;
			z->ey = e->y1;
			z->next = 0;
			return z;
		}
		// the edge passed in here does not cross the vertical line at x or the vertical line at x+1
		// (i.e. it has already been clipped to those)
		void tt___handle_clipped_edge(float *scanline, int x, std::shared_ptr<TTActiveEdge> e, float x0, float y0, float x1, float y1)
		{
			if (y0 == y1) return;
			must(y0 < y1);
			must(e->sy <= e->ey);
			if (y0 > e->ey) return;
			if (y1 < e->sy) return;
			if (y0 < e->sy) {
				x0 += (x1-x0) * (e->sy - y0) / (y1-y0);
				y0 = e->sy;
			}
			if (y1 > e->ey) {
				x1 += (x1-x0) * (e->ey - y1) / (y1-y0);
				y1 = e->ey;
			}
			
			if (x0 == x)
				must(x1 <= x+1);
			else if (x0 == x+1)
				must(x1 >= x);
			else if (x0 <= x)
				must(x1 <= x);
			else if (x0 >= x+1)
				must(x1 >= x+1);
			else
				must(x1 >= x && x1 <= x+1);
			
			if (x0 <= x && x1 <= x)
				scanline[x] += e->direction * (y1-y0);
			else if (x0 >= x+1 && x1 >= x+1)
				;
			else {
				must(x0 >= x && x0 <= x+1 && x1 >= x && x1 <= x+1);
				scanline[x] += e->direction * (y1-y0) * (1-((x0-x)+(x1-x))/2); // coverage = 1 - average x position
			}
		}
		
		void tt___fill_active_edges_new(float *scanline, float *scanline_fill, int len, std::shared_ptr<TTActiveEdge> e, float y_top)
		{
			float y_bottom = y_top+1;
			
			while (e) {
				// brute force every pixel
				
				// compute intersection points with top & bottom
				must(e->ey >= y_top);
				
				if (e->fdx == 0) {
					float x0 = e->fx;
					if (x0 < len) {
						if (x0 >= 0) {
							tt___handle_clipped_edge(scanline,(int) x0,e, x0,y_top, x0,y_bottom);
							tt___handle_clipped_edge(scanline_fill-1,(int) x0+1,e, x0,y_top, x0,y_bottom);
						} else {
							tt___handle_clipped_edge(scanline_fill-1,0,e, x0,y_top, x0,y_bottom);
						}
					}
				} else {
					float x0 = e->fx;
					float dx = e->fdx;
					float xb = x0 + dx;
					float x_top, x_bottom;
					float sy0,sy1;
					float dy = e->fdy;
					must(e->sy <= y_bottom && e->ey >= y_top);
					
					// compute endpoints of line segment clipped to this scanline (if the
					// line segment starts on this scanline. x0 is the intersection of the
					// line with y_top, but that may be off the line segment.
					if (e->sy > y_top) {
						x_top = x0 + dx * (e->sy - y_top);
						sy0 = e->sy;
					} else {
						x_top = x0;
						sy0 = y_top;
					}
					if (e->ey < y_bottom) {
						x_bottom = x0 + dx * (e->ey - y_top);
						sy1 = e->ey;
					} else {
						x_bottom = xb;
						sy1 = y_bottom;
					}
					
					if (x_top >= 0 && x_bottom >= 0 && x_top < len && x_bottom < len) {
						// from here on, we don't have to range check x values
						
						if ((int) x_top == (int) x_bottom) {
							float height;
							// simple case, only spans one pixel
							int x = (int) x_top;
							height = sy1 - sy0;
							must(x >= 0 && x < len);
							scanline[x] += e->direction * (1-((x_top - x) + (x_bottom-x))/2)  * height;
							scanline_fill[x] += e->direction * height; // everything right of this pixel is filled
						} else {
							float y_crossing, step, sign, area;
							// covers 2+ pixels
							if (x_top > x_bottom) {
								// flip scanline vertically; signed area is the same
								sy0 = y_bottom - (sy0 - y_top);
								sy1 = y_bottom - (sy1 - y_top);
								std::swap(sy0, sy1);
								std::swap(x_bottom, x_top);
								std::swap(x0, xb);
								//								dx = -dx; // never read
								dy = -dy;
							}
							
							int x1 = (int) x_top;
							int x2 = (int) x_bottom;
							// compute intersection with y axis at x1+1
							y_crossing = (x1+1 - x0) * dy + y_top;
							
							sign = e->direction;
							// area of the rectangle covered from y0..y_crossing
							area = sign * (y_crossing-sy0);
							// area of the triangle (x_top,y0), (x+1,y0), (x+1,y_crossing)
							scanline[x1] += area * (1-((x_top - x1)+(x1+1-x1))/2);
							
							step = sign * dy;
							for (int x = x1+1; x < x2; ++x) {
								scanline[x] += area + step/2;
								area += step;
							}
							y_crossing += dy * (x2 - (x1+1));
							
							must(fabs(area) <= 1.01f);
							
							scanline[x2] += area + sign * (1-((x2-x2)+(x_bottom-x2))/2) * (sy1-y_crossing);
							
							scanline_fill[x2] += sign * (sy1-sy0);
						}
					} else {
						// if edge goes outside of box we're drawing, we require
						// clipping logic. since this does not match the intended use
						// of this library, we use a different, very slow brute
						// force implementation
						int x;
						for (x=0; x < len; ++x) {
							// cases:
							//
							// there can be up to two intersections with the pixel. any intersection
							// with left or right edges can be handled by splitting into two (or three)
							// regions. intersections with top & bottom do not necessitate case-wise logic.
							//
							// the old way of doing this found the intersections with the left & right edges,
							// then used some simple logic to produce up to three segments in sorted order
							// from top-to-bottom. however, this had a problem: if an x edge was epsilon
							// across the x border, then the corresponding y position might not be distinct
							// from the other y segment, and it might ignored as an empty segment. to avoid
							// that, we need to explicitly produce segments based on x positions.
							
							// rename variables to clearly-defined pairs
							float y0 = y_top;
							float x1 = (float) (x);
							float x2 = (float) (x+1);
							float x3 = xb;
							float y3 = y_bottom;
							
							// x = e->x + e->dx * (y-y_top)
							// (y-y_top) = (x - e->x) / e->dx
							// y = (x - e->x) / e->dx + y_top
							float y1 = (x - x0) / dx + y_top;
							float y2 = (x+1 - x0) / dx + y_top;
							
							if (x0 < x1 && x3 > x2) {         // three segments descending down-right
								tt___handle_clipped_edge(scanline,x,e, x0,y0, x1,y1);
								tt___handle_clipped_edge(scanline,x,e, x1,y1, x2,y2);
								tt___handle_clipped_edge(scanline,x,e, x2,y2, x3,y3);
							} else if (x3 < x1 && x0 > x2) {  // three segments descending down-left
								tt___handle_clipped_edge(scanline,x,e, x0,y0, x2,y2);
								tt___handle_clipped_edge(scanline,x,e, x2,y2, x1,y1);
								tt___handle_clipped_edge(scanline,x,e, x1,y1, x3,y3);
							} else if (x0 < x1 && x3 > x1) {  // two segments across x, down-right
								tt___handle_clipped_edge(scanline,x,e, x0,y0, x1,y1);
								tt___handle_clipped_edge(scanline,x,e, x1,y1, x3,y3);
							} else if (x3 < x1 && x0 > x1) {  // two segments across x, down-left
								tt___handle_clipped_edge(scanline,x,e, x0,y0, x1,y1);
								tt___handle_clipped_edge(scanline,x,e, x1,y1, x3,y3);
							} else if (x0 < x2 && x3 > x2) {  // two segments across x+1, down-right
								tt___handle_clipped_edge(scanline,x,e, x0,y0, x2,y2);
								tt___handle_clipped_edge(scanline,x,e, x2,y2, x3,y3);
							} else if (x3 < x2 && x0 > x2) {  // two segments across x+1, down-left
								tt___handle_clipped_edge(scanline,x,e, x0,y0, x2,y2);
								tt___handle_clipped_edge(scanline,x,e, x2,y2, x3,y3);
							} else {  // one segment
								tt___handle_clipped_edge(scanline,x,e, x0,y0, x3,y3);
							}
						}
					}
				}
				e = e->next;
			}
		}
		
		// directly AA rasterize edges w/o supersampling
		void tt___rasterize_sorted_edges(Bitmap *result, TTEdge *e, int n, int vsubsample, int off_x, int off_y, void *userdata)
		{
			//			TTHeadHeap hh = { 0, 0, 0 };
			std::shared_ptr<TTActiveEdge> active;
			int y,j=0, i;
			float  *scanline, *scanline2;
			std::vector<float> scanline_data;
			
			STBTT__NOTUSED(vsubsample);

			scanline_data.resize((result->w*2+1));
			scanline = scanline_data.data();
			
			scanline2 = scanline + result->w;
			
			y = off_y;
			e[n].y0 = (float) (off_y + result->h) + 1;
			
			while (j < result->h) {
				// find center of pixel for this scanline
				float scan_y_top    = y + 0.0f;
				float scan_y_bottom = y + 1.0f;
				std::shared_ptr<TTActiveEdge>*step = &active;
				
				memset(scanline , 0, result->w*sizeof(scanline[0]));
				memset(scanline2, 0, (result->w+1)*sizeof(scanline[0]));
				
				// update all active edges;
				// remove all active edges that terminate before the top of this scanline
				while (*step) {
					auto z = *step;
					if (z->ey <= scan_y_top) {
						*step = z->next; // delete from list
						must(z->direction);
						z->direction = 0;
						//						TTHeadHeap_free(&hh, z);
					} else {
						step = &((*step)->next); // advance through list
					}
				}
				
				// insert all edges that start before the bottom of this scanline
				while (e->y0 <= scan_y_bottom) {
					if (e->y0 != e->y1) {
						auto z = tt___new_active(e, off_x, scan_y_top, userdata);
						if (z != NULL) {
							if (j == 0 && off_y != 0) {
								if (z->ey < scan_y_top) {
									// this can happen due to subpixel positioning and some kind of fp rounding error i think
									z->ey = scan_y_top;
								}
							}
							must(z->ey >= scan_y_top); // if we get really unlucky a tiny bit of an edge can be out of bounds
							// insert at front
							z->next = active;
							active = z;
						}
					}
					++e;
				}
				
				// now process all active edges
				if (active)
					tt___fill_active_edges_new(scanline, scanline2+1, result->w, active, scan_y_top);
				
				{
					float sum = 0;
					for (i=0; i < result->w; ++i) {
						float k;
						int m;
						sum += scanline2[i];
						k = scanline[i] + sum;
						k = (float) fabs(k)*255 + 0.5f;
						m = (int) k;
						if (m > 255) m = 255;
						result->pixels[j*result->w + i] = (unsigned char) m;
					}
				}
				// advance all the edges
				step = &active;
				while (*step) {
					auto z = *step;
					z->fx += z->fdx; // advance to position for current scanline
					step = &((*step)->next); // advance through list
				}
				
				++y;
				++j;
			}
			
			//			TTHeadHeap_cleanup(&hh, userdata);
		}
		
		void tt___rasterize(Bitmap *result, std::vector<Point2> & pts, std::vector<int> & wcount, int windings, float scale_x, float scale_y, float shift_x, float shift_y, int off_x, int off_y, int invert, void *userdata)
		{
			float y_scale_inv = invert ? -scale_y : scale_y;
			std::vector<TTEdge> e;
			int i,j,k,m;
			
			int vsubsample = 1;
			
			// vsubsample should divide 255 evenly; otherwise we won't reach full opacity
			
			// now we have to blow out the windings into explicit edge lists
			int sz = 0;
			for (i=0; i < windings; ++i)
				sz += wcount[i];
			
			e.resize(sz+1);

			int n = 0;
			
			m=0;
			for (i=0; i < windings; ++i) {
				Point2 *p = pts.data() + m;
				m += wcount[i];
				j = wcount[i]-1;
				for (k=0; k < wcount[i]; j=k++) {
					int a=k,b=j;
					// skip the edge if horizontal
					if (p[j].y == p[k].y)
						continue;
					// add edge from j to k to the list
					e[n].invert = 0;
					if (invert ? p[j].y > p[k].y : p[j].y < p[k].y) {
						e[n].invert = 1;
						a=j; b=k;
					}
					e[n].x0 = p[a].x * scale_x + shift_x;
					e[n].y0 = (p[a].y * y_scale_inv + shift_y) * vsubsample;
					e[n].x1 = p[b].x * scale_x + shift_x;
					e[n].y1 = (p[b].y * y_scale_inv + shift_y) * vsubsample;
					++n;
				}
			}
			
			// now sort the edges by their highest point (should snap to integer, and then by x)
			//STBTT_sort(e, n, sizeof(e[0]), TTEdge_compare);
			tt___sort_edges(e.data(), n);
			
			// now, traverse the scanlines and find the intersections on each scanline, use xor winding rule
			tt___rasterize_sorted_edges(result, e.data(), n, vsubsample, off_x, off_y, userdata);
		}
		
		
		void tt__Rasterize(Bitmap *result, float flatness_in_pixels, std::vector<TTVertex> & vertices, int num_verts, float scale_x, float scale_y, float shift_x, float shift_y, int x_off, int y_off, int invert, void *userdata)
		{
			float scale            = scale_x > scale_y ? scale_y : scale_x;
			int winding_count      = 0;
			std::vector<int> winding_lengths;
			auto windings = tt__FlattenCurves(vertices, num_verts, flatness_in_pixels / scale, &winding_lengths, &winding_count, userdata);

			tt___rasterize(result, windings, winding_lengths, winding_count, scale_x, scale_y, shift_x, shift_y, x_off, y_off, invert, userdata);
		}
		
		int tt__GetGlyphShape(int glyph_index, std::vector<TTVertex> *pvertices)
		{
			if (!info->cff.size)
				return tt___GetGlyphShapeTT(glyph_index, pvertices);
			else
				return tt___GetGlyphShapeT2(glyph_index, pvertices);
		}
		
		
		int tt__GetGlyphBitmapSubpixel(Bitmap & gbm, float scale_x, float scale_y, float shift_x, float shift_y, int glyph)
		{
			int ix0,iy0,ix1,iy1;
			std::vector<TTVertex> vertices;
			int num_verts = tt__GetGlyphShape(glyph, &vertices);
			
			if (scale_x == 0) scale_x = scale_y;
			if (scale_y == 0) {
				if (scale_x == 0) {
					return 0;
				}
				scale_y = scale_x;
			}
			
			tt__GetGlyphBitmapBoxSubpixel(glyph, scale_x, scale_y, shift_x, shift_y, &ix0,&iy0,&ix1,&iy1);
			
			// now we get the size
			gbm.w = (ix1 - ix0);
			gbm.h = (iy1 - iy0);
			gbm.x = ix0;
			gbm.y = iy0;
			gbm.pixels.clear();
			
			if (gbm.w && gbm.h) {
				gbm.pixels.resize(gbm.w * gbm.h);
				tt__Rasterize(&gbm, 0.35f, vertices, num_verts, scale_x, scale_y, shift_x, shift_y, ix0, iy0, 1, info->userdata);
			}
			return 1;
		}

		int tt__GetGlyphBox(int glyph_index, int *x0, int *y0, int *x1, int *y1)
		{
			Iterator data = m_info.data;

			if (info->cff.size) {
				tt___GetGlyphInfoT2(glyph_index, x0, y0, x1, y1);
			} else {
				int g = tt___GetGlyfOffset(glyph_index);
				if (g < 0) return 0;
				
				if (x0) *x0 = toInt16(data + g + 2);
				if (y0) *y0 = toInt16(data + g + 4);
				if (x1) *x1 = toInt16(data + g + 6);
				if (y1) *y1 = toInt16(data + g + 8);
			}
			return 1;
		}
		
		void tt__GetGlyphBitmapBoxSubpixel(int glyph, float scale_x, float scale_y,float shift_x, float shift_y, int *ix0, int *iy0, int *ix1, int *iy1)
		{
			int x0=0,y0=0,x1,y1; // =0 suppresses compiler warning
			if (!tt__GetGlyphBox(glyph, &x0,&y0,&x1,&y1)) {
				// e.g. space character
				if (ix0) *ix0 = 0;
				if (iy0) *iy0 = 0;
				if (ix1) *ix1 = 0;
				if (iy1) *iy1 = 0;
			} else {
				// move to integral bboxes (treating pixels as little squares, what pixels get touched)?
				if (ix0) *ix0 = (int)floor( x0 * scale_x + shift_x);
				if (iy0) *iy0 = (int)floor(-y1 * scale_y + shift_y);
				if (ix1) *ix1 = (int)ceil ( x1 * scale_x + shift_x);
				if (iy1) *iy1 = (int)ceil (-y0 * scale_y + shift_y);
			}
		}


		void initFont(std::vector<uint8_t> data) /* noexcept(false) */ override
		{
			m_info.data = std::move(data);
			tt__InitFont_internal();
		}

		int getXAdvance(int glyph, float height) override {
			int advance = 0;
			tt__GetGlyphHMetrics(glyph, &advance, nullptr);
			return (int)(advance * height / m_metrics.height + 0.5f);
		}

		Bitmap getGlyphBitmap(int glyph, float height) override
		{
			Bitmap gbm;
			if(glyph <= 0) return gbm;

			musts(height > 0, "invalid arg height");
			float scale = height / m_metrics.height;
			if(tt__GetGlyphBitmapSubpixel(gbm, scale, scale, 0.0f, 0.0f, glyph))
			{
				int advance = 0;
				tt__GetGlyphHMetrics(glyph, &advance, nullptr);
				gbm.x_advance = (int)(advance * scale + 0.5f);
			}
			return gbm;
		}


		VMetrics getFontMetrics() override {
			return m_metrics;
		}

		float getScale(float height)
		{
			return (float) height / m_metrics.height;
		}

		int getGlyphIndex(int code) override
		{
			Iterator data = info->data;
			uint32_t index_map = info->index_map;
			uint16_t format = toUint16(data + index_map + 0);
			if (format == 0) { // apple byte encoding

				/// Format 0 was the standard mapping subtable used on older Macintosh
				///  platforms but is not required on newer Apple platforms.

				int32_t bytes = toUint16(data + index_map + 2);
				if (code < bytes-6)
					return toUint8(data + index_map + 6 + code);
				return 0;
			} else if (format == 2 || format == 8) {
				Zen::LogE("No support high-byte mapping, format=[%d]", (int)format);
				// @TODO: high-byte mapping for japanese/chinese/korean

				/// https://docs.microsoft.com/en-us/typography/opentype/otspec182/cmap
				/// Format 2: High-byte mapping through table. This subtable format
				///  was created for “double-byte” encodings following the national
				///  character code standards used for Japanese, Chinese, and Korean
				///  characters. These code standards use a mixed 8-/16-bit encoding.
				///  This format is not commonly used today.
				///
				///  Subtable format 8 was designed to support Unicode supplementary-plane
				///   characters in UTF-16 encoding, though it is not commonly used.

				return 0;
			} else if (format == 4) {
				/// This is the standard character-to-glyph-index mapping subtable for fonts
				///  that support only Unicode Basic Multilingual Plane characters (U+0000 to U+FFFF).

				// standard mapping for windows fonts: binary search collection of ranges
				uint16_t segcount = toUint16(data+index_map+6) >> 1;
				uint16_t searchRange = toUint16(data+index_map+8) >> 1;
				uint16_t entrySelector = toUint16(data+index_map+10);
				uint16_t rangeShift = toUint16(data+index_map+12) >> 1;

				// do a binary search of the segments
				uint32_t endCount = index_map + 14;
				uint32_t search = endCount;

				if (code > 0xffff)
					return 0;

				// they lie from endCount .. endCount + segCount
				// but searchRange is the nearest power of two, so...
				if (code >= toUint16(data + search + rangeShift*2))
					search += rangeShift*2;

				// now decrement to bias correctly to find smallest
				search -= 2;
				while (entrySelector) {
					uint16_t end;
					searchRange >>= 1;
					end = toUint16(data + search + searchRange*2);
					if (code > end)
						search += searchRange*2;
					--entrySelector;
				}
				search += 2;

				{
					uint16_t offset, start;
					uint16_t item = (uint16_t) ((search - endCount) >> 1);

					must(code <= toUint16(data + endCount + 2*item));
					start = toUint16(data + index_map + 14 + segcount*2 + 2 + 2*item);
					if (code < start)
						return 0;

					offset = toUint16(data + index_map + 14 + segcount*6 + 2 + 2*item);
					if (offset == 0)
						return (uint16_t) (code + toInt16(data + index_map + 14 + segcount*4 + 2 + 2*item));

					return toUint16(data + offset + (code-start)*2 + index_map + 14 + segcount*6 + 2 + 2*item);
				}
			} else if (format == 6) {
				/// Format 6 was designed to map 16-bit characters to glyph indexes
				///  when the character codes for a font fall into a single contiguous range.

				uint32_t first = toUint16(data + index_map + 6);
				uint32_t count = toUint16(data + index_map + 8);
				if ((uint32_t) code >= first && (uint32_t) code < first+count)
					return toUint16(data + index_map + 10 + (code - first)*2);
				return 0;
			}  else if (format == 12 || format == 13) {

				/// Subtable format 13 has the same structure as format 12;
				///  it differs only in the interpretation of the startGlyphID/glyphID fields.
				/// Subtable format 12 is the standard character-to-glyph-index mapping
				///  subtable for fonts supporting Unicode character repertoires that include
				///   supplementary-plane characters (U+10000 to U+10FFFF).
				uint32_t ngroups = toUint32(data+index_map+12);
				int32_t low,high;
				low = 0; high = (int32_t)ngroups;
				// Binary search the right group.
				while (low < high) {
					int32_t mid = low + ((high-low) >> 1); // rounds down, so low <= mid < high
					uint32_t start_char = toUint32(data+index_map+16+mid*12);
					uint32_t end_char = toUint32(data+index_map+16+mid*12+4);
					if ((uint32_t) code < start_char)
						high = mid;
					else if ((uint32_t) code > end_char)
						low = mid+1;
					else {
						uint32_t start_glyph = toUint32(data+index_map+16+mid*12+8);
						if (format == 12)
							return start_glyph + code-start_char;
						else // format == 13
							return start_glyph;
					}
				}
				Zen::LogE("not found! codepoint=[%d], format=[%d]", (int)code, (int)format);
				return 0; // not found
			}
			// @TODO
			Zen::LogE("format=[%d] not supported", (int)format);
			return 0;
		}
	};

	std::shared_ptr<TrueType> TrueType::Create()
	{
		auto tt = std::shared_ptr<TrueType>(new TrueType_i);
		return tt;
	}
}
